package 二叉树;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
public class Solution116 {
    public static void main(String[] args) {
//        TreeNode treeNode = new TreeNode(1);
//        TreeNode treeNode1 = new TreeNode(2);
//        TreeNode treeNode2 = new TreeNode(3);
//        treeNode.left = treeNode1;
//        treeNode.right = treeNode2;
        Node3 node3 = new Node3();
        System.out.println(connect(node3));

    }

    public static Node3 connect(Node3 root) {
        if (root == null) {
            return root;
        }
        Queue<Node3> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node3 cur = queue.peek();
            int size = queue.size();
            int i = 0;
            while (size > 0) {
                Node3 next = queue.poll();
                if (next != null) {
                    if (next.left != null) {
                        queue.offer(next.left);
                    }
                    if (next.right != null) {
                        queue.offer(next.right);
                    }
                    if (i == 0) {
                        i++;
                    } else {
                        cur.next = next;
                        cur = next;
                    }

                }
                size--;
            }
        }
        return root;
    }


}
